﻿module Sieve

open System
open System.Collections

let primes = 
    let a = ResizeArray [ 2 ]
    
    let grow() = 
        let p0 = a.[a.Count - 1] + 1
        let b = Array.create p0 true
        for di in a do
            let rec loopA i = 
                if i < b.Length then 
                    b.[i] <- false
                    loopA (i + di)
            
            let i0 = p0 / di * di
            loopA (if i0 < p0 then i0 + di - p0
                  else i0 - p0)
        for i = 0 to b.Length - 1 do
            if b.[i] then a.Add(p0 + i)

    fun n -> 
        while n >= a.Count do
            grow()
        a.[n]

let primes3 max =
    Seq.initInfinite(fun i -> primes i) |> Seq.takeWhile (fun p -> p <= max)
    

let findPrimes max = 
    seq { 
        yield 2L
        let maxSquareRoot = int (sqrt (float max))
//        let primes = Array.create (max + 1) true
        let primes = new BitArray(max + 1, true)

        for n in 3..2..maxSquareRoot do
            if primes.[n] then 
                for i in n * n..2 * n..max do
                    primes.[i] <- false

        for n in 3..2..max do
            if primes.[n] then 
                yield int64 n
    }

//let findPrimes2 max =
////    let generator state =
////        let p = fst state
////        let ray = snd state
////        ray.[p] = false
////
////        Some(state, state)
//
////    let initState = 
//
//    Seq.unfold (fun state -> 
//            let p = fst state
//            let ray = snd state
//            ray.[p] <- false
//
//            Some(p + 1, (p, ray))
//        ) , 
//        (2, new BitArray(max + 1, true))

let countPrimes generator =
    Seq.length generator


let primes2 max = 
    let array = new BitArray(max + 1, true)
    //    let array =  Array.create max true
    let lastp = Math.Sqrt(float max) |> int
    seq { 
        for p in 2..lastp do
            if array.[p] then 
                yield p
                for pm in p * p..p..max - 1 do
                    array.[pm] <- false
    }
//    seq { for i in 2..max-1 do if array.[i] then yield i }
